// https://leetcode.cn/problems/minimum-height-trees/
// Created by ade on 2022/11/21.
// 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    // 通过不断削减最外层度数为1的节点，可以通过，但是 速度太慢了
    vector<int> findMinHeightTrees1(int n, vector <vector<int>> &edges) {
        vector<int> res = {};
        if (n < 2) {
            for (int i = 0; i < n; i++) res.push_back(i);
            return res;
        }
        unordered_map<int, unordered_set<int>> m = {};

        for (auto &e:edges) {
            m[e[0]].insert(e[1]);
            m[e[1]].insert(e[0]);
        }
        int num = m.size();
        while (m.size() > 2) {
            unordered_set<int> delElems = {};
            for (auto it = m.begin(); it != m.end();) {
                if (delElems.count(it->first) == 0 && it->second.size() == 1) {
                    int del = *it->second.begin(); // 度为1的节点
                    m[del].erase(it->first);
                    m.erase(it++);
                    delElems.insert(del);
                } else {
                    ++it;
                }
            }
        }
        for (auto &i : m) {
            res.push_back(i.first);
        }
        return res;
    }

    void show(unordered_set<int> &m) {
        for (auto i : m) {
            cout << i << ",";
        }
        cout << endl;
    }

    vector<int> findMinHeightTrees(int n, vector <vector<int>> &edges) {
        vector<int> res = {};
        if (n < 2) {
            for (int i = 0; i < n; i++) res.push_back(i);
            return res;
        }
        vector<int> count(n, 0);
        vector <vector<int>> elems(n);
        for (auto &e:edges) {
            count[e[0]]++;
            count[e[1]]++;
            elems[e[0]].push_back(e[1]);
            elems[e[1]].push_back(e[0]);
        }
        queue<int> q = {};
        for (int i = 0; i < n; i++) {
            if (count[i] == 1) q.push(i);
        }
        int leftCount = n;
        while (leftCount > 2) {
            int size = q.size();
            leftCount -= size;
            for (int i = 0; i < size; i++) {
                int f = q.front();
                q.pop();
                for (auto &v:elems[f]) {
                    if (--count[v] == 1) {
                        q.push(v);
                    }
                }
            }
        }
        while (!q.empty()) {
            res.push_back(q.front());
            q.pop();
        }
        return res;
    }
};

int main() {
    Solution so;
    vector <vector<int>> nums = {{3, 0},
                                 {3, 1},
                                 {3, 2},
                                 {3, 4},
                                 {5, 4}};
    auto a = so.findMinHeightTrees(6, nums);
    for (auto &i:a) cout << i << ",";
    cout << endl;

    return 0;
}